package sort;

import java.util.Arrays;

public class SevenSort_1 {
    public static void main(String[] args) {
        int n = 100000;
        int[] arr = SortHelper.genraRandomArray(n, 0, Integer.MAX_VALUE);
        int[] arr1 = SortHelper.arrCopy(arr);
        int[] arr2 = SortHelper.arrCopy(arr);
        int[] arr3 = SortHelper.arrCopy(arr);
        int[] arr4 = SortHelper.arrCopy(arr);
        int[] arr5 = SortHelper.arrCopy(arr);

        //测试
//        SortHelper.testSort(arr1, "selectionSort");//选择排序——直接选择排序
//        SortHelper.testSort(arr2, "selectionSortOP");// 双向选择排序
    //    SortHelper.testSort(arr3, "bubbleSort");//冒泡排序
        SortHelper.testSort(arr3, "insertionSort");//直接插入排序
        SortHelper.testSort(arr4, "insertionSortBS");//二分插入

//        int[] arr = {19,27,13,22,3,1,6,5,4,2,110,65,70,98,72};
//        //调用刚刚写的原地排序方法
//        insertionSort(arr);
//        System.out.println(Arrays.toString(arr));


    }

    /**
     * 选择排序——直接选择排序
     */
    public static void selectionSort(int[] arr){
        //最开始的无序区间[i...n）
        //有序区间是 【 】 为空

        for (int i = 0; i < arr.length; i++) {
            int min = i;//记录每次最小值索引
            for (int j = i + 1; j < arr.length; j++) {
                if(arr[min] > arr[j]){
                    min = j;
                }
            }//循环后找到了当前最小值索引
            swaq(arr, i, min);
        }
    }

    /**
     * 双向选择排序
     */
    public static void selectionSortOP(int[] arr){
        int low = 0;
        int high = arr.length - 1;

        while(low < high){
            int max = low;
            int min = low;//这里写成low可以让i写成 low + 1 少循环一次
            for (int i = low + 1; i <= high ; i++) {
                if(arr[min] > arr[i]){
                    min = i;
                }

                if(arr[max] > arr[i]){
                    max = i;
                }
            }//for
            swaq(arr, min, low);
            //有种特殊情况，当max索引在low上，就会被最小值交换时给移走
            if(max == low){
                max = min;
            }
            swaq(arr, max, high);

            low ++;
            high --;
        }

    }

    /**
     *  冒泡排序
     */
    public static void bubbleSort(int[] arr){
        //n - 1 个数排序好了，那么整个数组就排序好了，所以可以 - 1
        for (int i = 0; i <arr.length - 1; i++) {
            boolean isswaq = true;
            for (int j = 0; j < arr.length - i - 1; j++) {
                if(arr[j] > arr[j + 1]){
                    swaq(arr, j, j + 1);
                    isswaq = false;
                }
            }
            //如果某次遍历一次都没交换过元素，说明已经有序
            if(isswaq){
                break;
            }
        }
    }


    /**
     * 直接插入排序
     * 已排序区间[0..i)  => 默认第一个元素就是已经排好序的区间
     * 待排序区间[i...n)
     * @param arr
     */
    public static void insertionSort(int[] arr) {

        for (int i = 1; i < arr.length; i++) {
            //从后向前看
            for (int j = i; j > 0 && arr[j] < arr[j - 1] ; j--) {
                int tmp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = tmp;
//                if(arr[j] < arr[j - 1]){
//                    swaq(arr, j, j - 1);
//                }else{
//                    break;
//                }
            }

        }
    }

    /**
     * 二分插入排序
     */
    public static void insertionSortBS(int[] arr){
        // 排序区间[0~i)
        // 待排序区间[i...n)
        //默认第一个是已经排序好了的
        for (int i = 1; i < arr.length; i++) {

            int low = 0;
            int high = i - 1;
            int min = (low + high) / 2;
            while(low < high){
                if(arr[min] > arr[i]){
                    high = min - 1;
                }else if(arr[min] < arr[i]){
                    low = min + 1;
                }else{
                    break;
                }
                min = (low + high) / 2;
            }
            int val = arr[i];
            for (int j = i; j > min ; j++) {
                arr[j] = arr[j - 1];
            }
            arr[min] = val;

        }


    }



    /**
     * 传入数组和数组里两个索引，交换位置
     */
    private static void swaq(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }


}
